package edu.tamu.cse.teamproject1.Database.Parser;

import java.security.InvalidParameterException;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import edu.tamu.cse.teamproject1.Database.Tuple;
import edu.tamu.cse.teamproject1.Database.Exceptions.InvalidColumnException;
import edu.tamu.cse.teamproject1.Database.Exceptions.NullReferenceException;
import edu.tamu.cse.teamproject1.Database.Exceptions.SqlException;
import edu.tamu.cse.teamproject1.Database.Interfaces.IColumnDefinition;
import edu.tamu.cse.teamproject1.Database.Interfaces.IDatabaseTable;
import edu.tamu.cse.teamproject1.Database.Interfaces.ITuple;
import edu.tamu.cse.teamproject1.Database.Interfaces.ITupleElement;

/**
 * Filters result sets based on a WHERE clause
 * 
 * @author Christopher Weldon <chris@chrisweldon.net>
 * @since Release 0.1.0
 */
public class QueryFilter {
	/**
	 * Database table the filter should be applied to
	 */
	private IDatabaseTable _table;
	
	/**
	 * All other tables to filter data on
	 */
	private List<IDatabaseTable> allTables;
	
	/**
	 * Query that helps filter the results
	 */
	private String _filter;

	/**
	 * Returns a list of tuples with all of the records merged together based on the query
	 * 
	 * @param leftColumn
	 * @param rightColumn
	 * @param view
	 * @return List of joined tuples
	 */
	private List<ITuple> mergeJoinedRecords(String leftColumn, String rightColumn, 
			List<ITuple> tuples) {
		List<ITuple> tableLTuple = new ArrayList<ITuple>();
		List<ITuple> tableRTuple = new ArrayList<ITuple>();
		List<ITuple> mergedRecords = new ArrayList<ITuple>();
		
		// Fetch the column on which to match records
		for (ITuple tuple : tuples) {
			for (ITupleElement te : tuple.getAllElements()) {
				if (te.getColumnName().equals(leftColumn) && !te.isValueNull()) {
					tableLTuple.add(tuple);
					break;
				} else if (te.getColumnName().equals(rightColumn) && !te.isValueNull()) {
					tableRTuple.add(tuple);
					break;
				}
			}
		}
		
		// Determine which table is bigger. We will be returning the greater
		// number of records as tuples. 
		List<ITuple> gTuple = tableLTuple;
		List<ITuple> lTuple = tableRTuple;
		// Flip if our assumption is incorrect
		if (tableLTuple.size() < tableRTuple.size()) {
			gTuple = tableRTuple;
			lTuple = tableLTuple;
		}
		
		/*
		 * The following block of code will iterate through the list of left and
		 * right tuples and will match the records between them. The matching is
		 * done with preference to the left, meaning that it expects at most one
		 * record on the left set of tuples, and n number of records on the right
		 * set of tuples. 
		 * 
		 * The first inner for loop sets up the new tuple. It grabs the non-empty
		 * columns from the left set of tuples. The second inner loop will grab
		 * all of the tuples from the right set that match the column value of 
		 * the left tuple. The final loop creates all of the tuples from the matching
		 * right set by pairing the left tuple (already setup) with the values from
		 * the right. 
		 * 
		 * CAUTION: O(n^2 + 2*n^3)
		 */
		for (ITuple ltuple : gTuple) {
			ITuple newTuple = new Tuple();
			Object lvalue = null;
			for (ITupleElement lelem : ltuple.getAllElements()) {
				// Store the value for comparison in the for loop for the right tuple
				if (lelem.getColumnName().equals(leftColumn)) {
					lvalue = lelem.getValue();
				}
				// If the value is not null, add the element
				if (!lelem.isValueNull()) {
					newTuple.addTupleElement(lelem);
				}
			}
			// Process the matches
			List<ITuple> rTupleMatches = new ArrayList<ITuple>();
			for (ITuple rtuple : lTuple) {
				for (ITupleElement relem : rtuple.getAllElements()) {
					if (relem.getColumnName().equals(rightColumn)) {
						if (lvalue.equals(relem.getValue())) {
							rTupleMatches.add(rtuple);
						}
					}
				}
			}
			// Go back and merge the records together
			for (ITuple rtuple : rTupleMatches) {
				ITuple cloneTuple = (ITuple)newTuple.clone();
				for (ITupleElement relem : rtuple.getAllElements()) {
					if (!relem.isValueNull()) {
						cloneTuple.addTupleElement(relem);
					}
				}
				mergedRecords.add(cloneTuple);
			}
		}
		
		return mergedRecords;
	}
	
	/**
	 * Checks to see if the operator passed is a valid operator or not
	 * 
	 * @param operator
	 * @return Is the string an operator?
	 */
	protected boolean checkOperator(String operator) {
		String temp = operator.toUpperCase();
		if (temp.equals("AND") || temp.equals("OR") || temp.equals("NOT") ||
			temp.equals("ALL") || temp.equals("ANY")) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * Removes all non-value spaces from the query string
	 * 
	 * @param query
	 * @return Query without spaces
	 * @todo Fix to handle IN, EXISTS, ANY, and ALL
	 */
	protected String trimSpaces(String query) {
		String trimmedQuery = "";
		boolean inValue = false;
		String[] tokens = query.split(" ");
		for (String token : tokens) {
			if (checkOperator(token) || token.contains("IN(") || token.contains("EXISTS(")) {
				// Anything but OR, AND, and NOT get spaces around them
				if (token.contains("IN(") || token.contains("EXISTS(")) {
					trimmedQuery += " " + token;
				} else if (!token.equals("OR") && !token.equals("AND") && !token.equals("NOT")) {
					trimmedQuery += " " + token + " ";
				} else {
					trimmedQuery += token;
				}
			} else if (token.contains("'")) {
				// If the token is strictly a value, then add and continue
				if (token.startsWith("'") && token.endsWith("'")) {
					trimmedQuery += token;
				} else {
					if (inValue) {
						trimmedQuery += " " + token;
					} else {
						trimmedQuery += token;
					}
					inValue = !inValue;
				}
			} else {
				if (inValue) {
					trimmedQuery += " ";
				}
				trimmedQuery += token;
			}
		}
		
		return trimmedQuery;
	}
	
	/**
	 * Parses the filter query using a couple of different stacks
	 * 
	 * This is probably the most complex method in this class. It will break apart
	 * the query character by character and recreate the sub-queries to as to be
	 * able to stack the requests in order of precedence. 
	 * 
	 * We convert the query into one without spaces (except for values) so that
	 * we don't have to deal with spaces. 
	 * 
	 * @param query
	 * @return Stack containing order of operations
	 */
	protected Stack<String> parseFilterQuery(String query) {
		// Setup the values we'll need during parsing
		Stack<String> tempOperationStack = new Stack<String>();
		Stack<String> operationStack = new Stack<String>();
		String tempColName = "";
		String tempColValue = "";
		String tempOperator = "";
		boolean inValue = false, inQuoted = false;
		
		// Get rid of non-essential spaces
		query = this.trimSpaces(query);
		
		// Proceed with parsing character by character
		for (char c : query.toCharArray()) {
			if (c == ' ' && !inValue) {
				// We've entered a space before a non-standard operator (e.g. ANY, ALL, etc.). 
				// Clear the buffers by adding them to the stack and continue
				if (tempColName != "") {
					tempOperationStack.push(tempColName);
					tempColName = "";
				}
				if (tempOperator != "") {
					tempOperationStack.push(tempOperator);
					tempOperator = "";
				}
				if (tempColValue != "") {
					tempOperationStack.push(tempColValue);
					tempColValue = "";
				}
				inValue = true;
			} else if (c == '(' && !inValue && !inQuoted) {
				// This is the beginning of a clause. We take everything that's on the tempColName,
				// tempOperator, and tempColValue and push down onto the stack, in that order. This 
				// helps to clear the state, as there should not be any lingering values in those buffers
				
				// Check if the name buffer is empty
				if (tempColName != "") {
					tempOperationStack.push(tempColName);
					tempColName = "";
				}
				
				// Check if the operator buffer is empty
				if (tempOperator != "") {
					tempOperationStack.push(tempOperator);
					tempOperator = "";
				}
				
				// Push the opening brace onto the stack for later consumption. Mark that we're not in a value
				tempOperationStack.push("(");
				inValue = false;
			} else if (c == ')' && !inQuoted) {
				// This is the ending of a clause. We take everything from the temporary stack, pop it off
				// and push it down onto the new stack. This follows from the PREFIX notation learned in
				// CPSC221. Before popping off the stack, we have to check to make sure there are no outstanding
				// values to push onto the stack.
				
				// The only case that we want to avoid this is if we have ANY() or ALL()
				if (tempColValue.contains("ANY(") || tempColValue.contains("ALL(") ||
						tempColValue.contains("IN(") || tempColValue.contains("EXISTS(")) {
					tempColValue += c;
					tempOperationStack.push(tempColValue);
					tempColValue = "";
					continue;
				}
				
				// Need to first push the value down onto the stack and clear its temp storage
				if (tempColValue != "") {
					tempOperationStack.push(tempColValue);
					tempColValue = "";
				}
				
				// Pop top 3 elements (name, operator, and value) off the temp stack, assemble them, 
				// and push onto the new stack
				String tempVal = "";
				while (tempOperationStack.peek() != "(") {
					if (tempOperationStack.peek().contains("EXISTS(") || tempOperationStack.peek().contains("IN(")) {
						tempVal = " " + tempOperationStack.pop() + tempVal;
					} else {
						// Assemble in reverse
						tempVal = tempOperationStack.pop() + tempVal;
					}
				}
				operationStack.push(tempVal);
				// Pop the "(" back off the stack
				tempOperationStack.pop();
				inValue = false;
			} else if (inValue && c != '\'') {
				// Take all characters as long as we're in value
				tempColValue += c;
			} else if (c == '\'') {
				// In the event that we run across a single quote, which is an indicator of values,
				// then we need to flip some flags around to make the process state-aware. Before
				// updating the state, we need to get the name and operator values onto the stack. 
				if (tempColName != "") {
					tempOperationStack.push(tempColName);
					tempColName = "";
				}
				if (tempOperator != "") {
					tempOperationStack.push(tempOperator);
					tempOperator = "";
				}
				
				// Update the state and save the value
				inValue = !inValue;
				inQuoted = !inQuoted;
				tempColValue += c;
			} else if (c == '!' || c == '=' || c == '>' || c == '<') {
				// We're checking for basic operators. By this point, if one of
				// the previous cases did not match, then we're not inValue, meaning
				// it's safe to try to match the operators. Before storing the operator,
				// push names down onto the stack. 
				if (tempColName != "") {
					tempOperationStack.push(tempColName);
					tempColName = "";
				}
				// We're collecting an operator
				tempOperator += c;
			} else {
				// Finally, we assume that we're gathering column names. Check if the operator
				// is empty or not, and push down onto the stack if it isn't empty. 
				if (tempOperator != "") {
					// Push the operator onto the stack and clear it
					tempOperationStack.push(tempOperator);
					tempOperator = "";
					inValue = true;
					tempColValue += c;
				} else {
					// No need to freak - we're just collecting a column name
					tempColName += c;
					// We actually collected an operator if this is true. Push it
					// onto the stack.
					if (checkOperator(tempColName)) {
						tempOperationStack.push(tempColName);
						if (!tempColName.equals("AND") &&
								!tempColName.equals("OR") &&
								!tempColName.equals("NOT")) {
							inValue = true;
						}
						tempColName = "";
					}
				}
			}
		}
			
		// Check for missing values and push them onto the temp stack. 
		if (tempColValue != "") {
			tempOperationStack.push(tempColValue);
			tempColValue = "";
		}
		
		// Get everything off the temp stack (that's not a parenthesis) and push down onto the main stack
		String tempVal = "";
		while (tempOperationStack.size() > 0) {
			String tempPop = tempOperationStack.pop();
			if (tempPop != "(" && tempPop != ")") {
				if (tempPop.contains("IN(") || tempPop.contains("EXISTS(")) {
					tempPop = " " + tempPop;
				}
				tempVal = tempPop + tempVal;
			}
		}
		if (tempVal != "") {
			operationStack.push(tempVal.trim());
		}
		return operationStack;
	}
	
	/**
	 * Performs an ALL search with a list of given search rows
	 * 
	 * The columnValue will contain the ALL(tableName) that needs parsing. This 
	 * will return a list of tuples that match. It makes use of the allTables
	 * private variable to do searching on other tables. 
	 * 
	 * @param searchRows
	 * @param columnName
	 * @param columnValue
	 * @param comparator
	 * @return
	 */
	protected List<ITuple> searchAllMatching(List<ITuple> searchRows, String columnName,
			Object columnValue, String comparator) throws SqlException {
		List<ITuple> matches = new ArrayList<ITuple>();
		Pattern pat = Pattern.compile("^ALL\\((.*)\\)$");
		Matcher match = pat.matcher(columnValue.toString().trim());
		if (!match.matches()) {
			throw new SqlException("Unable to match the ALL pattern.");
		}
		
		String tableForMatching = match.group(1);
		if (tableForMatching.trim().equals("")) {
			throw new SqlException("No table to perform matching on.");
		}
		
		// Find the table to match
		IDatabaseTable matchTable = null;
		for (IDatabaseTable table : this.allTables) {
			if (table.getName().equals(tableForMatching)) {
				matchTable = table;
				break;
			}
		}
		
		// Error out if we can't find the table
		if (matchTable == null) {
			throw new SqlException("Cannot find table " + tableForMatching);
		}
		
		// Match all the records
		for (ITuple tuple : searchRows) {
			boolean allMatch = true;
			for (ITupleElement element : tuple.getAllElements()) {
				if (!element.getColumnName().equals(columnName)) {
					continue;
				}
				// If we're here, we've found the column we're to be doing the
				// comparison. Start comparing values. Remember this table should
				// have only *1* column.
				for (ITuple matchTuple : matchTable.getAllTuples()) {
					ITupleElement matchElem = matchTuple.getAllElements().get(0);
					if (!element.getColumnType().equals(matchElem.getColumnType())) {
						throw new SqlException("Cannot perform matching on differing column types.");
					}
					
					switch (element.getColumnType()) {
					case character:
					case varchar:
						if (!ComparatorParser.compare(element.getValue().toString(), 
								matchElem.getValue().toString(), 
								comparator)) {
							allMatch = false;
							break;
						}
						break;
					case integer:
						if (!ComparatorParser.compare(Integer.parseInt(element.getValue().toString()), 
								Integer.parseInt(matchElem.getValue().toString()), 
								comparator)) {
							allMatch = false;
							break;
						}
						break;
					case floating:
						if (!ComparatorParser.compare(Float.parseFloat(element.getValue().toString()), 
								Float.parseFloat(matchElem.getValue().toString()), 
								comparator)) {
							allMatch = false;
							break;
						}
						break;
					case date:
						Date elemDate = (Date)element.getValue();
						Date colValue = (Date)matchElem.getValue();
						if (!ComparatorParser.compare(elemDate, colValue, comparator)) {
							allMatch = false;
							break;
						}
						break;
					default:
						// TODO: Figure out how to handle this situation
						break;
					}
				}
			}
			if (allMatch) {
				matches.add(tuple);
			}
		}
		
		// return the results
		return matches;
	}
	
	/**
	 * Performs an ANY search with a list of given search rows
	 * 
	 * The columnValue will contain the ANY(tableName) that needs parsing. This 
	 * will return a list of tuples that match. It makes use of the allTables
	 * private variable to do searching on other tables. 
	 * 
	 * @param searchRows
	 * @param columnName
	 * @param columnValue
	 * @param comparator
	 * @return
	 */
	protected List<ITuple> searchAnyMatching(List<ITuple> searchRows, String columnName,
			Object columnValue, String comparator) throws SqlException {
		List<ITuple> matches = new ArrayList<ITuple>();
		Pattern pat = Pattern.compile("^ANY\\((.*)\\)$");
		Matcher match = pat.matcher(columnValue.toString().trim());
		if (!match.matches()) {
			throw new SqlException("Unable to match the ANY pattern.");
		}
		
		String tableForMatching = match.group(1);
		if (tableForMatching.trim().equals("")) {
			throw new SqlException("No table to perform matching on.");
		}
		
		// Find the table to match
		IDatabaseTable matchTable = null;
		for (IDatabaseTable table : this.allTables) {
			if (table.getName().equals(tableForMatching)) {
				matchTable = table;
				break;
			}
		}
		
		// Error out if we can't find the table
		if (matchTable == null) {
			throw new SqlException("Cannot find table " + tableForMatching);
		}
		
		// Match all the records
		for (ITuple tuple : searchRows) {
			for (ITupleElement element : tuple.getAllElements()) {
				if (!element.getColumnName().equals(columnName)) {
					continue;
				}
				// If we're here, we've found the column we're to be doing the
				// comparison. Start comparing values. Remember this table should
				// have only *1* column.
				for (ITuple matchTuple : matchTable.getAllTuples()) {
					ITupleElement matchElem = matchTuple.getAllElements().get(0);
					if (!element.getColumnType().equals(matchElem.getColumnType())) {
						throw new SqlException("Cannot perform matching on differing column types.");
					}
					
					switch (element.getColumnType()) {
					case character:
					case varchar:
						if (ComparatorParser.compare(element.getValue().toString(), 
								matchElem.getValue().toString(), 
								comparator)) {
							matches.add(tuple);
							break;
						}
						break;
					case integer:
						if (ComparatorParser.compare(Integer.parseInt(element.getValue().toString()), 
								Integer.parseInt(matchElem.getValue().toString()), 
								comparator)) {
							matches.add(tuple);
							break;
						}
						break;
					case floating:
						if (ComparatorParser.compare(Float.parseFloat(element.getValue().toString()), 
								Float.parseFloat(matchElem.getValue().toString()), 
								comparator)) {
							matches.add(tuple);
							break;
						}
						break;
					case date:
						Date elemDate = (Date)element.getValue();
						Date colValue = (Date)matchElem.getValue();
						if (ComparatorParser.compare(elemDate, colValue, comparator)) {
							matches.add(tuple);
							break;
						}
						break;
					default:
						// TODO: Figure out how to handle this situation
						break;
					}
				}
			}
		}
		
		// return the results
		return matches;
	}
	
	/**
	 * filters the list of tuples through the operators IN or EXISTS
	 * @param searchRows
	 * @param columnName
	 * @param operationText
	 * @return List of Tuples according to the IN or EXISTS sql text
	 * @throws SqlException
	 */
	protected List<ITuple> getMatchingRows(List<ITuple> searchRows, String columnName,
			String operationText) throws SqlException {
		
		/*check to make sure the operation text is in the correct format*/
		Pattern operatorLine = Pattern.compile("^([A-Z]*)\\((.*)\\)$");
		Matcher operatorMatch = operatorLine.matcher(operationText.trim());
		if (!operatorMatch.matches()) {
			throw new SqlException("Unable to parse select query.");
		}

		/*separate the operationText from the operation and the tableName*/
		String operation = operatorMatch.group(1);
		String origTableName = operatorMatch.group(2);
		
		/*call the appropriate function*/
		if(operation.equals("IN")){
			return getINRows(searchRows, columnName, origTableName);
		}
		else if(operation.equals("EXISTS")){
			return getEXISTSRows(searchRows, columnName, origTableName);			
		}
		else{
			return searchRows;
		}
	}
	
	/**
	 * Retrieves a list of matching elements from a list of elements
	 * 
	 * This method takes several arguments (the first of which being a list of
	 * Tuples to filter) and will apply a comparator to a column and return
	 * only the matching tuples.
	 * 
	 * If a columnName is being searched that doesn't exist in the table, then
	 * an InvalidColumnException is thrown.
	 * 
	 * @param searchRows Records to filter
	 * @param columnName Name of the column to apply a filter
	 * @param columnValue Value of the column to check (may also contain ANY or ALL)
	 * @param comparator How the values should be evaluated? (<, <=, >, =, etc.)
	 * @return List of matching elements
	 * @throws InvalidParameterException, InvalidColumnException, NullReferenceException
	 */
	protected List<ITuple> getMatchingRows(List<ITuple> searchRows, String columnName, 
			Object columnValue, String comparator) 
			throws InvalidParameterException, InvalidColumnException, NullReferenceException, SqlException {
		// Do some sanity checking
		if (searchRows == null || searchRows.size() == 0) {
			// Return an empty array list if we have nothing to search.
			return new ArrayList<ITuple>();
		}
		if (columnName == null || columnName.equals("")) {
			throw new InvalidParameterException("columnName must not be null or empty.");
		}
		if (columnValue == null || columnValue.toString().equals("")) {
			throw new InvalidParameterException("columnValue must not be null or empty.");
		}
		if (comparator == null || comparator.equals("")) {
			throw new InvalidParameterException("comparator must not be null or empty.");
		}
		
		// Quick check to see if the columnName exists. Throw an exception if not.
		if (!this.checkColumnNameExists(columnName)) {
			throw new InvalidColumnException("Column name " + columnName + " does not exist.");
		}
		
		// Check for ANY or ALL
		List<ITuple> tuples = new ArrayList<ITuple>();
		if (columnValue.toString().contains("ANY(")) {
			tuples = this.searchAnyMatching(searchRows, columnName, columnValue, comparator);
		} else if (columnValue.toString().contains("ALL(")) {
			tuples = this.searchAllMatching(searchRows, columnName, columnValue, comparator);
		} else {
			// Iterate over all of the tuples given to us and add to the tuple stack above 
			// if the values match the requested operator
			for (ITuple tuple : searchRows) {
				List<ITupleElement> tupleElements = tuple.getAllElements();
				for (ITupleElement element : tupleElements) {
					if (element.getColumnName().equals(columnName)) {
						// TODO: Cast to the appropriate type and compare values
						switch (element.getColumnType()) {
						case character:
						case varchar:
							if (ComparatorParser.compare(element.getValue().toString(), columnValue.toString(), comparator)) {
								tuples.add(tuple);
							}
							break;
						case integer:
							if (ComparatorParser.compare(Integer.parseInt(element.getValue().toString()), Integer.parseInt(columnValue.toString()), comparator)) {
								tuples.add(tuple);
							}
							break;
						case floating:
							if (ComparatorParser.compare(Float.parseFloat(element.getValue().toString()), Float.parseFloat(columnValue.toString()), comparator)) {
								tuples.add(tuple);
							}
							break;
						case date:
							Date elemDate = (Date)element.getValue();
							Date colValue = (Date)columnValue;
							if (ComparatorParser.compare(elemDate, colValue, comparator)) {
								tuples.add(tuple);
							}
							break;
						default:
							// TODO: Figure out how to handle this situation
							break;
						}
					}
				}
			}
		}
		
		return tuples;
	}
	
	/**
	 * Checks if the column name exists in the table
	 * 
	 * @param columnName Name of column to check for
	 * @return true if column name exists
	 * @throws NullReferenceException if database table is not set
	 */
	protected boolean checkColumnNameExists(String columnName) 
		throws NullReferenceException {
		// Sanity check
		if (this._table == null) {
			throw new NullReferenceException("Database table not set.");
		}
		
		// Iterate over the column definitions and try to find the column
		boolean columnNameExists = false;
		for (IColumnDefinition column : this._table.getColumnLists()) {
			if (column.getColumnName().equals(columnName)) {
				columnNameExists = true;
				break;
			}
		}
		return columnNameExists;
	}
	
	/**
	 * This method will look down the stack and assemble any join queries necessary 
	 * for the full assimilation of data in a join query
	 * 
	 * @param queryStack
	 * @return Join query stack (indicator if join queries were detected)
	 */
	protected Stack<String> createJoinQueries(Stack<String> queryStack) throws SqlException {
		try {
			Stack<String> tempJoinSearchStack = new Stack<String>();
			while (queryStack.size() > 0) {
				tempJoinSearchStack.push(queryStack.pop());
				String topOfStack = tempJoinSearchStack.peek();
				// If this is an operator, we can skip processing
				if (this.checkOperator(topOfStack)) {
					continue;
				}
				if (topOfStack.contains("EXISTS(") || topOfStack.contains("IN(")) {
					continue;
				}
				String[] op = this.splitKeyValuePair(topOfStack);
				if (op[1].contains(".") && !op[1].matches("^[\\.0-9]*$")) {
					// This is a join query. We need to push down an OR query
					// to fetch all matching records from the other table
					// XXX: In order for this to work, there must be another query
					// down on one of the stacks for us to compare
					String matchedQuery = "";
					for (int i = 0; i < queryStack.size(); i++) {
						String tmpQuery = queryStack.get(i);
						String[] tmpOps = this.splitKeyValuePair(tmpQuery);
						if (tmpOps[0].trim().equals(op[1].trim()) || 
								tmpOps[0].trim().equals(op[0].trim())) {
							matchedQuery = tmpQuery;
							break;
						}
					}
					if (matchedQuery.equals("")) {
						// Try out temp stack
						for (int i = 0; i < tempJoinSearchStack.size(); i++) {
							String tmpQuery = tempJoinSearchStack.get(i);
							// We don't want to operate on the join query that's in the stack
							if (tmpQuery.equals(topOfStack)) {
								continue;
							}
							// We also aren't comparing to operators
							if (this.checkOperator(tmpQuery)) {
								continue;
							}
							// Check to ignore EXISTS or IN
							if (tmpQuery.contains("IN(") || tmpQuery.contains("EXISTS(")) {
								continue;
							}
							// Compare and see if we find the value matching
							String[] tmpOps = this.splitKeyValuePair(tmpQuery);
							if (tmpOps[0].trim().equals(op[1].trim()) ||
									tmpOps[0].trim().equals(op[0].trim())) {
								matchedQuery = tmpQuery;
								break;
							}
						}
					}
					// If it equals nothing, we're matching all records from the join.
					// Otherwise, we need to assemble a new query 
					if (!matchedQuery.equals("")) {
						// Check whether we're comparing the left or right side of the query
						// and assemble an additional query to be put on the stack.
						String[] nextQueryOps = this.splitKeyValuePair(matchedQuery);
						String nextNewQuery = "";
						if (nextQueryOps[0].equals(op[1])) {
							nextNewQuery = op[0] + nextQueryOps[2] + nextQueryOps[1];
						} else if (nextQueryOps[0].equals(op[0])) {
							nextNewQuery = op[1] + nextQueryOps[2] + nextQueryOps[1];
						}
						// Push back the new query and an OR clause
						tempJoinSearchStack.push("OR");
						tempJoinSearchStack.push(nextNewQuery);
					} else {
						// There were no matches, so we need to search for all records
						// from both sides of the table
						// Split the topOfStack
						String[] stackSplit = topOfStack.split("=");
						tempJoinSearchStack.push("OR");
						String[] tableSplit = stackSplit[0].split("\\.");
						tempJoinSearchStack.push(stackSplit[0] + "!=0");
						tempJoinSearchStack.push("OR");
						tableSplit = stackSplit[1].split("\\.");
						tempJoinSearchStack.push(stackSplit[1] + "!=0");
					}
				}
			}
			
			// Go back and put all of the queries back into the original stack
			while (tempJoinSearchStack.size() > 0) {
				queryStack.push(tempJoinSearchStack.pop());
			}
		} catch (Exception e) {
			throw new SqlException("Unable to process join search.");
		}
		
		return queryStack;
	}
	
	/**
	 * Refactored Method for performing a query where EXISTS or IN comes into play
	 * 
	 * The whereStatement should be in the format of EXISTS(tableName) or 
	 * columnName IN(tableName). 
	 * 
	 * @param whereStatement
	 * @return List of records that match the parameters of the SQL query
	 * @throws SqlException
	 */
	protected List<ITuple> existsOrInQueryBridge(String whereStatement) throws SqlException {
		// The columnName may be empty when passed to the getMatchingRows
		// But queryString will always be the IN/EXISTS complete with 
		// parenthetical table name
		String columnName = "";
		String queryString = "";
		Pattern pat = Pattern.compile("^(.*)IN\\((.*)\\)$");
		Matcher match = pat.matcher(whereStatement);
		// Get the columnName from IN, if using IN
		if (match.matches()) {
			columnName = match.group(1).trim();
			queryString = "IN(" + match.group(2).trim() + ")";
		} else {
			queryString = whereStatement.trim();
		}
		
		// Perform the query
		List<ITuple> tempResult = this.getMatchingRows(this._table.getAllTuples(), 
				columnName, queryString);
		return tempResult;
	}
	
	/**
	 * Takes the query stack and performs the query
	 * 
	 * This method will make use of two stacks, one to place waiting filters queries
	 * (when trying to find the operator such as AND, OR, and NOT). The other stack
	 * is the original input stack.
	 * 
	 * @param queryStack
	 * @return List of results from the query
	 * @throws SqlException
	 * @todo Test this method
	 */
	protected List<ITuple> performQuery(Stack<String> queryStack) throws SqlException {
		Stack<String> tempStack = new Stack<String>();
		Stack<String> joinStack = new Stack<String>();
		Stack<List<ITuple>> resultStack = new Stack<List<ITuple>>();
		
		// We need to look through the list of queries for joins
		queryStack = this.createJoinQueries(queryStack);
		
		// Reverse the queryStack order
		while (queryStack.size() > 0) {
			tempStack.push(queryStack.pop());
		}
		queryStack = tempStack;
		tempStack = new Stack<String>();
		
		try {
			while (queryStack.size() > 0) {
				tempStack.push(queryStack.pop());
				if (this.checkOperator(tempStack.peek())) {
					// If we just pushed down an operator, then process the results on the stack
					String operator = tempStack.pop();
					if (queryStack.size() > 0) {
						tempStack.push(queryStack.pop());
					}
					// Pull everything off the temp stack and process, 
					// storing the results in the result stack
					while (tempStack.size() > 0) {
						String whereStatement = tempStack.pop();
						
						if (this.checkOperator(whereStatement)) {
							// Swap else ignore
							if (queryStack.size() > 0) {
								String temp = queryStack.pop();
								queryStack.push(whereStatement);
								whereStatement = temp;
							} else {
								continue;
							}
						}
						
						// Check for EXISTS or IN
						if (whereStatement.trim().contains("EXISTS(") ||
								whereStatement.trim().contains("IN(")) {
							List<ITuple> tempResult = this.existsOrInQueryBridge(whereStatement);
							resultStack.push(tempResult);
							continue;
						}
						
						// If we get here, then we're operating on pseudo-standard
						// key/value pairs
						String[] operation = this.splitKeyValuePair(whereStatement);
						if (operation[1].contains(".") && !operation[1].matches("^[\\.0-9]*$")) {
							// Push down onto the joinStack and continue
							joinStack.push(whereStatement);
							// Check if the next thing on the stack is an operator
							// because it should be an OR (from the createJoinQuery)
							if (this.checkOperator(queryStack.peek())) {
								operator = queryStack.pop();
								continue;
							}
						} else {
							List<ITuple> tempResult = this.getMatchingRows(this._table.getAllTuples(), 
									operation[0], operation[1], operation[2]);
							resultStack.push(tempResult);
						}
					}
					// Pop the top 2 results off and perform the operation on them
					if (resultStack.size() > 1) {
						List<ITuple> result1 = resultStack.pop();
						List<ITuple> result2 = resultStack.pop();
						resultStack.push(this.mergeResults(result1, result2, operator));
					} else {
						// Swap the top with the operator
						if (queryStack.size() > 0) {
							String top = queryStack.pop();
							queryStack.push(operator);
							queryStack.push(top);
						}
					}
				} else {
					while (tempStack.size() > 0) {
						String whereStatement = tempStack.pop();
						// Check for EXISTS or IN
						if (whereStatement.trim().contains("EXISTS(") ||
								whereStatement.trim().contains("IN(")) {
							List<ITuple> tempResult = this.existsOrInQueryBridge(whereStatement);
							resultStack.push(tempResult);
							continue;
						}
						// If we get here, then we're operating on pseudo-standard
						// key/value pairs
						String[] operation = this.splitKeyValuePair(whereStatement);
						if (operation[1].contains(".") && !operation[1].matches("^[\\.0-9]*$")) {
							// Push down onto the joinStack and continue
							joinStack.push(whereStatement);
							if (this.checkOperator(queryStack.peek())) {
								// pop it off and ignore.
								queryStack.pop();
							}
						} else {
							List<ITuple> tempResult = this.getMatchingRows(this._table.getAllTuples(), 
									operation[0], operation[1], operation[2]);
							resultStack.push(tempResult);
						}
					}
				}
			}
			
			// Perform joining of rows
			if (joinStack.size() > 0) {
				String clause = joinStack.pop();
				String[] operation = this.splitKeyValuePair(clause);
				List<ITuple> currentTuples = resultStack.pop();
				List<ITuple> mergedTuples = this.mergeJoinedRecords(operation[0], operation[1], currentTuples);
				resultStack.push(mergedTuples);
			}
		} catch (InvalidColumnException e) { 
			throw new SqlException("A column requested has an invalid name.");
		} catch (NullReferenceException e) {
			throw new SqlException("Unable to perform the query.", e);
		}
		
		// The value to return should be the top of the result stack
		return resultStack.pop();
	}
	
	/**
	 * Merges the results of the tuple lists together, removing duplicates
	 * 
	 * @param result1 Result set 1
	 * @param result2 Result set 2
	 * @param operator The merging operation
	 * @return List of merged tuple lists
	 * @todo Test this method
	 */
	protected List<ITuple> mergeResults(List<ITuple> result1, List<ITuple> result2, String operator) {
		List<ITuple> mergedResults = new ArrayList<ITuple>();
		if (operator.equals("OR")) {
			// Add all from tuple list 1 and pick up the missing from result2
			mergedResults.addAll(result1);
			for (ITuple tuple : result2) {
				if (!mergedResults.contains(tuple)) {
					mergedResults.add(tuple);
				}
			} 
		} else if (operator.equals("AND")) {
			// Add all tuples common to both result sets
			for (ITuple tuple : result1) {
				if (result2.contains(tuple)) {
					mergedResults.add(tuple);
				}
			}
		} else if (operator.equals("NOT")) {
			// Add tuples from result1 that are not in result 2
			for (ITuple tuple : result1) {
				if (!result2.contains(tuple)) {
					mergedResults.add(tuple);
				}
			}
		}
		
		return mergedResults;
	}
	
	/**
	 * Takes a key-value pair and splits into an array
	 * 
	 * The resulting array should have the following elements:
	 * 
	 *  0 = key
	 *  1 = value
	 *  2 = operator
	 * 
	 * @param query
	 * @return Array of key value pairs (should be 3 elements)
	 * @todo Fix this method to account for ANY, ALL, IN, or EXISTS
	 */
	protected String[] splitKeyValuePair(String kvpair) {
		String[] exploded = kvpair.split("[!=<>]+");
		String[] newExploded = new String[exploded.length+1];
		newExploded[0] = exploded[0];
		newExploded[1] = exploded[1];
		String temp = kvpair.replace(exploded[0], "");
		temp = temp.replace(exploded[1], "");
		newExploded[2] = temp;
		return newExploded;
	}
	
	/**
	 * filters the the List of Tuples by the IN SQL statement
	 * 
	 * @param searchRows
	 * @param columnName
	 * @param tableName
	 * @return List of Tuples filtered by the IN sql statement according to the
	 * the table: tableName and the column: columnName
	 */
	protected List<ITuple> getINRows(List<ITuple> searchRows, String columnName,
			String tableName) throws SqlException{
		IDatabaseTable searchTable = null;
		List<ITuple> generatedTuples = new ArrayList<ITuple>();
		
		/*search for the table with the name: tableName*/
		for(IDatabaseTable t: allTables){
			if(t.getName().equals(tableName)){
				searchTable = t;
				break;
			}
		}
		if(searchTable == null)
			throw new SqlException("No searchable table in the IN statement found!");
		if(searchTable.getColumnLists().size() != 1){
			throw new SqlException("The searchable table has more then 1 column");
		}
		
		/*loop through the rows of the tuples and add them to the generatedTuples if
		 * they match up to the searchTable*/
		for(ITuple r: searchRows){
			/*search each tupleElement for the column "columnName"*/
		tuplesearch:
			for(ITupleElement e: r.getAllElements()){
				if(e.getColumnName().equals(columnName)){
					/*search for the matching columnName in the searchTable to compare*/
					for(ITuple t: searchTable.getAllTuples()){
						ITupleElement se = t.getAllElements().get(0);
						if (se == null) {
							throw new SqlException("Unable to obtain single column on Tuple.");
						}
						// If the columnName contains ., then split and take the literal column
						// name. We don't want to get the table name match
						String nestedTableColumn = columnName;
						if (nestedTableColumn.contains(".")) {
							String[] colSplit = nestedTableColumn.split("\\.");
							nestedTableColumn = colSplit[1];
						}
						/*are the tuples matching? if so add tuple to generatedTuples*/
						if(se.getColumnName().equals(nestedTableColumn) && 
								e.getValue().equals(se.getValue())){
							generatedTuples.add(r);
							break tuplesearch;
						}
					}
				}
			}
		}
		
		return generatedTuples;
	}
	
	/**
	 * filters the list of tuples according to the EXISTS SQL Statement
	 * 
	 * @param searchRows
	 * @param columnName
	 * @param tableName
	 * @return List<ITuple>, all tuples from searchRows if one of the tuples match
	 * the EXISTS SQL Statement
	 */
	protected List<ITuple> getEXISTSRows(List<ITuple> searchRows, String columnName,
			String tableName) throws SqlException {
		IDatabaseTable searchTable = null;
		/*search for the table with the name: tableName*/
		for(IDatabaseTable t: allTables){
			if(t.getName().equals(tableName)){
				searchTable = t;
				break;
			}
		}
		if(searchTable == null)
			throw new SqlException("No searchable table in the IN statement found!");
		if(searchTable.getColumnLists().size() != 1){
			throw new SqlException("The searchable table has more then 1 column");
		}
		
		/*loop through the rows of the tuples and add them to the generatedTuples if
		 * they match up to the searchTable*/
		for(ITuple r: searchRows){
			/*search each tupleElement for the column "columnName"*/
			for(ITupleElement e: r.getAllElements()){
				if(e.getColumnName().equals(columnName)){
					/*search for the matching columnName in the searchTable to compare*/
					for(ITuple t: searchTable.getAllTuples()){
						ITupleElement se = t.getAllElements().get(0);
						if (se == null) {
							throw new SqlException("Unable to get single column for tuple.");
						}
						// If the columnName contains ., then split and take the literal column
						// name. We don't want to get the table name match
						String nestedTableColumn = columnName;
						if (nestedTableColumn.contains(".")) {
							String[] colSplit = nestedTableColumn.split("\\.");
							nestedTableColumn = colSplit[1];
						}
						/*are the tuples matching? if so add return searchRows*/
						if(se.getColumnName().equals(nestedTableColumn) && 
								e.getValue().equals(se.getValue())){
							return searchRows;
						}
					}
				}
			}
		}
		
		// Clear all search rows and return since we had no matches.
		searchRows.clear();
		return searchRows;
	}
	
	/**
	 * Constructs a query filter object
	 */
	public QueryFilter() {}
	
	/**
	 * Constructor accepting a Database Table as an argument
	 * 
	 * @param IDatabaseTable table
	 */
	public QueryFilter(IDatabaseTable table) {
		this._table = table;
	}
	
	/**
	 * Applies a filter locally
	 * 
	 * The application doesn't do anything initially. It's application becomes
	 * apparent later when the consumer of this object retrieves the list of
	 * results. 
	 * 
	 * @param String queryFilter
	 */
	public void applyFilter(String queryFilter) {
		this._filter = queryFilter;
	}
	
	/**
	 * Sets the database table that will be used for consuming results
	 * 
	 * @param table
	 */
	public void setTable(IDatabaseTable table) {
		this._table = table;
	}
	
	/**
	 * Retrieves a list of results
	 * 
	 * This method will fetch a list of rows from the databaseTable based on the
	 * criterion specified in the filter. 
	 * 
	 * @return List of rows matching the query filter
	 * @throws NullReferenceException, SqlException
	 */
	public List<ITuple> fetchResults() throws NullReferenceException, SqlException {
		if (this._table == null) {
			throw new NullReferenceException("No table to operate on.");
		}
		
		// Return all the tuples if there's no filter to be applied
		if (this._filter == null || this._filter.equals("")) {
			return this._table.getAllTuples();
		} else {
			// Parse the query and make the comparison on the operators
			Stack<String> resultComparators = this.parseFilterQuery(this._filter);
			try {
				return this.performQuery(resultComparators);
			} catch (SqlException e) {
				throw e;
			}
		}
	}
	
	/**
	 * Sets all tables that are to be consumed by various cross-join queries. 
	 * @param tables
	 */
	public void setAllTables(List<IDatabaseTable> tables) {
		this.allTables = tables;
	}
}	